// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Quicksort using a variation of the Lomuto partition scheme
namespace ConsoleApp1
{
    class Program
    {
        static List<string> quicksort(List<string> items)
        {
            // A single item does not need sorting
            if (items.Count <= 1)
            {
                return items;
            }
            else
            {
                // Set the pointer position and pivot to be the last item
                int pointer = 0;
                int pivot = items.Count - 1;
                string pivot_value = items[items.Count - 1];
                string temp;
                int temp_pointer;
                // Partitioning step
                while (pointer != pivot)
                {
                    // Put pivot item in position
                    if ((string.Compare(items[pointer], items[pivot]) > 0) && (pointer < pivot) || ((string.Compare(items[pointer], items[pivot]) < 0) && (pointer > pivot)))
                    {
                        temp = items[pointer];
                        items[pointer] = items[pivot];
                        items[pivot] = temp;
                        temp_pointer = pointer;
                        pointer = pivot;
                        pivot = temp_pointer;
                    }
                    // Move the pointer
                    if (pointer < pivot)
                    {
                        pointer = pointer + 1;
                    }
                    else
                    {
                        pointer = pointer - 1;
                    }
                }

                // Divide and conquer left and right of the pivot
                List<string> new_list = new List<string>();
                new_list.AddRange(quicksort(items.GetRange(0, pointer)));
                new_list.Add(items[pointer]);
                new_list.AddRange(quicksort(items.GetRange(pointer + 1, items.Count - 1 - pointer)));
                return new_list;
            }
        }

        // Main program starts here
        static void Main(string[] args)
        {
            List<string> items = new List<string> { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = quicksort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
